public class Solution1416 {
    public int numberOfArrays(String s, int k) {
        int[] f=new int[s.length()+1];
        f[0]=1;
        for (int i=1;i<=s.length();i++){
            StringBuilder stringBuilder=new StringBuilder();
            for (int j=i-1;j>=0;j--){
                stringBuilder.insert(0,s.charAt(j));
                long l=Long.parseLong(stringBuilder.toString());
                if (l>=1 && l<=k && s.charAt(j)!='0'){
                    f[i]=(f[i]+f[j])%1000000007;
                }
                if (l>k || stringBuilder.length()>10){
                    break;
                }
            }
        }
        return f[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1416().numberOfArrays("604516296181603152696",696));
    }
}
